def TowerOfHanoi(n, source, target, auxiliary):
    """
    分别有从大到小摆放的盘子 source 和 target
    现在要求将所有的盘子从source柱移动到target柱，每次只能移动一个盘子，并且不能将大的盘子放在小的盘子上。
        算法思路：借助auxiliary进行递归解决。
            首先将前n-1个盘子从A柱借助C柱移动到B柱；
            然后将第n个盘子从A柱移动到C柱；
            最后将前n-1个盘子从B柱借助A柱移动到C柱
    """
    if n > 0:
        # 将 n-1 个盘子从 source 移动到 auxiliary
        TowerOfHanoi(n-1, source, auxiliary, target)
        # 将第 n 个盘子从 source 移动到 target
        print(" 将盘子 {} 从 {} 移动到 {}".format(n, source, target))
        # 将 n-1 个盘子从 auxiliary 移动到 target
        TowerOfHanoi(n-1, auxiliary, target, source)


# 调用函数，例如：将 3 个盘子从 A 柱移动到 C 柱
TowerOfHanoi(1, 'A', 'C', 'B')


"""
-> 4  source->target
    -> 3  source->target
        -> 2  source->target
            -> 1  source->target
                 将盘子 1 从 A 移动到 B
            <- 1  auxiliary->target
             将盘子 2 从 A 移动到 C
            -> 1  source->target
                 将盘子 1 从 B 移动到 C
            <- 1  auxiliary->target
        <- 2  auxiliary->target
        将盘子 3 从 A 移动到 B
        -> 2  source->target
            -> 1  source->target
                将盘子 1 从 C 移动到 A
            <- 1  auxiliary->target
             将盘子 2 从 C 移动到 B
            -> 1  source->target
                将盘子 1 从 A 移动到 B
            <- 1  auxiliary->target
        <- 2  auxiliary->target
    <- 3  auxiliary->target
    将盘子 4 从 A 移动到 C
    -> 3  source->target
        -> 2  source->target
            -> 1  source->target
                将盘子 1 从 B 移动到 C
            <- 1  auxiliary->target
            将盘子 2 从 B 移动到 A
            -> 1  source->target
                将盘子 1 从 C 移动到 A
            <- 1  auxiliary->target
        <- 2  auxiliary->target
         将盘子 3 从 B 移动到 C
        -> 2  source->target
            -> 1  source->target
                将盘子 1 从 A 移动到 B
            <- 1  auxiliary->target
            将盘子 2 从 A 移动到 C
            -> 1  source->target
                将盘子 1 从 B 移动到 C
            <- 1  auxiliary->target
        <- 2  auxiliary->target
    <- 3  auxiliary->target
<- 4  auxiliary->target

"""




def is_safe(board, row, col):
    # 检查同一列是否有皇后互相冲突
    for i in range(row):
        if board[i][col] == 1:
            return False
    # 检查左上角到右下角的对角线是否有皇后互相冲突
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    # 检查右上角到左下角的对角线是否有皇后互相冲突
    for i, j in zip(range(row, -1, -1), range(col, len(board))):
        if board[i][j] == 1:
            return False
    return True


def solve_n_queens(board, row):
    if row >= len(board):
        return 1
    count = 0
    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1
            count += solve_n_queens(board, row + 1)
            board[row][col] = 0
    return count


def n_queens(n):
    board_n = [[0 for _ in range(n)] for _ in range(n)]
    return solve_n_queens(board_n, 0)


n = 8
print("八皇后问题的解决方案数量：", n_queens(n))


